2301. Иголка в стоге сена

Напишите программу, которая находит все совпадения заданного шаблона со входной строкой. Эта задача напоминает поиск иголки в стоге сена. Программа должна найти все местоположения иголки в стоге сена.

Вход. Состоит из нескольких тестов. Каждый тест состоит из трех строк, содержащих:

· длину иголки,

· саму иголку,

· стог сена.

Длина иголки не более 10000 символов. Стог сена не будем ограничивать в размерах – ваша программа должна читать его по мере обработки.

Тесты следуют один за другим, каждый занимает ровно три строки без разделителей.

Выход. Для каждого теста следует вывести все позиции вхождения иголки в стог сена. Если найдено совпадение, то результат должен содержать положение первого символа совпадения. Символы в стоге сена нумеруются с нуля.

Для каждого теста позиции совпадения следует отсортировать в порядке возрастания и вывести каждую из них в отдельной строке. Для двух различных тестов позиции совпадения должны быть разделены пустой строкой.

Пример входа	Пример выхода
2 na banananobano 6 foobar foo 9 foobarfoo barfoobarfoobarfoobarfoobarfoo	2 4 3 9 15 21

Пояснение: Обратите внимание на двойную пустую строку в выходном файле, так как не было найдено совпадение для второго теста

РЕШЕНИЕ

строки – Кнут-Моррис-Пратт

Анализ алгоритма

Для решения задачи необходимо реализовать алгоритм Кнута-Морриса-Пратта поиска шаблона в тексте.

Реализация алгоритма

Иголку будем хранить в символьном массиве word. Префикс – функцию для нее построим в массиве p.

#define MAX 10010

char word[MAX];

int p[MAX];

Функция MaxBorderArray вычисляет в массиве p префикс – функцию строки s.

void MaxBorderArray(char *s)

{

int i, j, len = strlen(s);

p[0] = 0;

for(i = 1; i < len; i++)

{

j = p[i - 1];

while ((j > 0) && (s[i] != s[j])) j = p[j - 1];

if (s[i] == s[j]) j++;

p[i] = j;

}

}

Функция kmp реализует алгоритм Кнута-Морриса-Пратта и выводит все начальные позиции совпадений. Шаблон (иголка) находится в массиве word. Текст имеет длину около 10 миллионов символов, считывается посимвольно.

void kmp(void)

{

int i, j;

char ch;

scanf("%c",&ch);

for(i = j = 0; ch != '\n'; i++)

{

while(j && (ch != word[j])) j = p[j - 1];

if (ch == word[j]) j++;

Если найдено совпадение – выводим положение его первого символа.

if (j == len)

printf("%d\n",i - j + 1);

Читаем следующий символ стога (текста).

scanf("%c",&ch);

}

}

Основная часть программы. Функция MaxBorderArray вычисляет префикс-функцию, которая используется в КМП.

scanf("%d\n",&len);

while(1)

{

gets(word); MaxBorderArray(word);

kmp();

if(scanf("%d\n",&len) != 1) break;

printf("\n");

}